
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1608. -- [Usaco2008 Dec]Jigsaw Puzzles -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1608: [Usaco2008 Dec]Jigsaw Puzzles</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>27&nbsp;&nbsp;<span class=green>Solved: </span>0<br>[<a href='submitpage.php?id=1608'>Submit</a>][<a href='problemstatus.php?id=1608'>Status</a>][<a href='bbs.php?id=1608'>Discuss</a>]</center><h2>Description</h2><div class=content>The cows have taken up alphabetical jigsaw puzzles. In these puzzles
with R (1 <= R <= 10) rows and C (1 <= C <= 10) columns, the edges
are not funny-shaped cardboard shapes but rather are letters.

Each piece has a serial number and 4 letters (or borders) that must
be aligned as in a regular jigsaw puzzle. The pseudo-letter '0'
(the digit 0) will represent a border (and a piece can have several
borders if it is a corner piece or even the top of column in a,
e.g., 4x1 puzzle).  Below is a set of six pieces (the borders are
marked with lines instead of '0's) assembled in one way (of many)
that completes the puzzle:

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

Note that each edge letter of each piece matches the border letter
of the piece adjacent to it; the borders appear properly on the top,
bottom, and sides.

Pieces are represented by a serial number and a clockwise list of
their four edges (where edges are the letters a..z and 0). Pieces
might require rotation when placed in the puzzle.

Given a set of pieces, find at least one way to assemble them into
a puzzle. Test data for puzzles with larger R and C are easier to
solve because they have a more varied set of edge letters.

奶牛们玩字母拼图游戏，拼图有R(1<=R<=10)行C(1<=C<=10)列，每个格子有上下左右4条边，
边可以是abcd四种字母或边界（用'0' 表示），如图是一种拼法。
注意到两个相邻格子所对的边上的字母互相匹配，边界出现在拼图的上下左右边缘上。
每个格子用序号表示，按顺时针方向给出它们的四条边，可以旋转。要求找出一组可行解。
输入 ： 第一行R,C。接下来2..R*C+1行，每行描述一个格子，第一个数是它的序号，接下来四个数为它的四条边。
输出 ： 共R*C行，第(i-1)*C+j行5个数，第一个数为放在（i，j)处的格子序号，接下来按上右下左的顺序为它的四条边。</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: R and C

* Lines 2..R*C+1: Each line contains five space-separated entities: an
        integer serial number and four edge identifiers

</div><h2>Output</h2><div class=content>* Lines 1..R*C: Line R*(i-1)+j describes the puzzle piece placed a row
        i, column j with an integer and five space-separated entities:
        the serial number of the puzzle piece and the four piece edge
        identifiers in the order top, right, bottom, left.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>2 3<br />
1 c d 0 0<br />
2 0 d b 0<br />
3 c 0 d a<br />
4 b a b 0<br />
5 d 0 0 e<br />
6 0 0 b e<br />
<br />
INPUT DETAILS:<br />
<br />
Describes the input puzzle although with some of the pieces rotated<br />
compared to the sample solution.<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>1 0 c d 0<br />
3 0 d a c<br />
5 0 0 e d<br />
2 d b 0 0<br />
4 a b 0 b<br />
6 e 0 0 b<br />
<br />
OUTPUT DETAILS:<br />
<br />
As shown in the diagram in the task text. Other solutions (like<br />
reflections) are possible; a grading program will check your answer.<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Silver'>Silver</a></p></div><center>[<a href='submitpage.php?id=1608'>Submit</a>][<a href='problemstatus.php?id=1608'>Status</a>][<a href='bbs.php?id=1608'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
